Enterprises increasingly need to store large amounts of data in data storage computing devices, or filers, and require that the data be accessible in an efficient manner. Data storage computing devices often implement a buffer cache as a repository for cached disk block reads and writes that are maintained in the form of buffers that can be used to service future reads to data storage blocks more efficiently. A buffer cache can be implemented in random access memory (RAM) media to provide relatively fast retrieval of buffer contents.
In order to optimize buffer cache performance, the buffers are maintained in a priority queue so that buffers that are expected to be least likely to be needed in the future can be quickly identified. Buffers can be prioritized based on the type of data represented by the buffer (e.g., a user file or system metadata), buffer tree level, or frequency of use of the buffer, for example. New buffers are continuously requested and lower priority buffers that are least likely to be needed in the future are evicted to service such requests.
Data storage computing devices are increasingly complex, and often have multiprocessing capabilities. One option to improve parallelism in a buffer cache system hosted on a multiprocessor data storage computing device is to associate buffers and recycle queues with threads for lockless processing. However, buffers associated with threads are not necessarily uniformly distributed or deprioritized after not being used for an extended time duration, referred to herein as aging. Accordingly, heuristic distributed algorithms have been developed for buffer cache operations, such as aging and scavenging, that facilitate buffer eviction or the return of buffers to a free pool.
In a distributed environment, heuristic-based aging algorithms may not always yield fair aging across threads. Aging within fixed queues may require visiting individual buffers to make an aging decision, making this an expensive operation. Additionally, current scavenging algorithms rely on an approximation for buffer priority and, therefore, often result in scavenging important buffers associated with one thread before less important buffers associated with another thread. Accordingly, current algorithms used to operate buffer caches have significant limitations and are not particularly effective.